package com.datastructure.test.maxlengthofincrementserial;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;

public class MaxLengthOfIncrementSerial {

    ArrayList<ArrayList<Integer>> res = new ArrayList<>();

    public static void main(String[] args) {
        MaxLengthOfIncrementSerial maxLengthOfIncrementSerial = new MaxLengthOfIncrementSerial();
        int [] data = {2,1,5,3,7,9};
        maxLengthOfIncrementSerial.LIS(data);
    }

    public int[] LIS (int[] arr) {
        // write code here
        int n=arr.length;
        //dp[i]表示以i位置元素结尾的最长上升子序列长度
        int[] dp=new int[n+1];
        //初始化为1
        Arrays.fill(dp,1);
        //记录最长子序列的长度
        int len=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                //如果小于arr[i]，则可以接在arr[i]前面
                if(arr[j]<arr[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            //计算最长子序列的长度
            len=Math.max(len,dp[i]);
        }

        int[] res=new int[len];
        //从后往前确定目标子序列的每一个值
        for(int i=n-1;i>=0;i--){
            if(dp[i]==len){
                res[--len]=arr[i];
            }
        }
        return res;
    }

    public int[] LIS1 (int[] arr) {
        int[] tail = new int[arr.length];
        int[] dp = new int[arr.length];
        tail[0] = arr[0];
        int end = 0;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > tail[end]) {
                tail[++end] = arr[i];
                dp[i] = end;
            }
            else {
                int l = 0;
                int r = end - 1;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (arr[i] > tail[mid] && arr[i] <= tail[mid + 1]) {
                        l = mid+1;
                        break;
                    } else if (arr[i] > tail[mid]) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                tail[l] = arr[i];
                dp[i] = l;
            }
        }
        // 寻找最小字典序
        int [] res = new int[end+1];
        int i = arr.length-1;

        for(;i>=0 && end >=0; i--){
            if(dp[i]==end){
                res[end] = arr[i];
                end--;
            }
        }

        return res;
    }

    private void insertValue(int i, int lastValue, int[] arr, Deque<Integer> deque) {
        for (int j = i+1; j < arr.length; j++) {
            if(arr[j]>lastValue){
                deque.add(arr[j]);
                insertValue(j,arr[j], arr,deque);
                deque.removeLast();
            }
        }
        res.add(new ArrayList<>(deque));
    }
}
